//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>
#include <iterator>


static void bubbleSortOptimization(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // isSwap 用来标记上一次冒泡的时候是否交换过。如果没有交换过, 那就是已经有序了。就退出外部循环。
    bool isSwap = true;
    for (int i = 0; (i < arr.size() - 1) && isSwap; ++i) {
        isSwap = false;
        for (int j = arr.size() - 1; j > i; --j) {
            // 在某一趟遍历冒泡中, 如果没有可交换的, 即序列已经有序了。那么 isSwap = false, 跳出外层循环。
            // 而如果一旦进行了交换, 则 isSwap = true, 那就需要进行下一趟遍历冒泡。
            if (arr[j - 1] > arr[j]) {
                std::swap( arr[j - 1], arr[j] );
                isSwap = true;
            }
        }
    }
}


/*
 * 每次交换后, 最小的数到了最前面。
 */
static void bubbleSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 外部循环的条件为什么是 arr.size() - 1 ?
    // todo 笔记: 因为当到 倒数第二个元素有序后, 这个序列就有序了。最后一个元素不需要排序了。这个条件和选择排序的外部循环一样的道理。
    //  当然循环的条件是 arr.size(); 也行那么就是 最后一个元素的时候: i = 4 此时内部循环中 j = 4, 内部循环的条件 j > i 不成立。
    //  所以不会执行内部循环。但是这样的话, 进行了一次 for循环 的判断, 这个判断是可以避免的。所以, 使用 arr.size() - 1; 作为
    //  外部循环的条件。
    for (int i = 0; i < arr.size() - 1; ++i) {
        for (int j = arr.size() - 1; j > i; --j) {
            if (arr[j - 1] > arr[j]) {
                std::swap( arr[j - 1], arr[j] );
            }
        }
    }
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr{3, 2, 5, 4, 1};
        bubbleSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }

    {
        std::vector<int> arr{3, 2, 5, 4, 1};
        bubbleSortOptimization( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }


    return 0;
}
